1. Field of the Invention
The present invention relates to semiconductor chips and, more particularly, to a system and method for calculating density maps for hierarchical chip designs.
2. Description of the Related Art
Density maps are used in the semiconductor industry as a metric for determining manufactured chip quality. Calculating a density map for various levels of the chip design is often required in the manufacturing process; such levels correspond to different processing steps or material layers, such as diffusion, metal interconnect, etc. The density map is computed to check layout ground rules dictated by process considerations. The density map is used to condition "fill shapes" to be added to a design for the purpose of making pattern density more even across the design. The density map may also be used to condition compensation algorithms (e.g., which modify the local widths of critical features) to compensate for process variations due to variations in pattern density.
The density map is also useful for determining other important scalar properties, for example, defect susceptibility, power dissipation, etc. for purposes of modeling and/or correction for these properties. The density map also is used to estimate yield loss due to densities that are too low or too high in metal layers of the design. The density map is further used to evaluate non-uniformities in height across the chip, due to variations in density, and its effect on CMP (chemical mechanical planarization). Density map is generally about 10% to about 50% for standard designs.
A density map is determined by computing a fraction of occupied area in a given area as described in Kahng et al., Int. Smp. of Phys. Des. 1998. The occupied area is the area occupied by a shape or shapes of, for example, a device such as a transistor or a diffusion region of the transistor. This problem is closely related to a measure problem. The measure problem seeks to find the area of a collection of rectangles, where overlapping regions are only counted once. An algorithm with complexity of O (N log N), where N is the number of rectangles, has been developed in the prior art to address the measure problem.
For real designs, the calculation of density maps is often more complex than the solutions described above. Chip designs include shapes that cannot always be represented by a set of rectangles without losing accuracy. Also, the measure for real designs must be found within many grid squares. Further, the prior art approach requires flattening the design which precludes its usage for very large designs, for example in memory chips. This also precludes usage of the prior approach in devices other than memory chips, for example in processors having on-chip cache, register files, repetitive usage of large standard cells, etc.
Therefore, a need exists for a system and method for determining density maps in a highly nested (hierarchical) form. A further need exists for providing a more efficient system and method for reducing running time and memory requirements for calculating density maps.